'''
二分查找（Binary Search），也称作折半查找算法，是一种在有序数组中查找某一特定元素的搜索算法。
以下是对二分查找的详细介绍及其时间、空间复杂度分析：
一、二分查找介绍
1. 基本原理
二分查找基于有序数组的特性，通过每次比较数组中间的元素与目标值，将搜索范围缩小一半，从而实现对数据的快速查找。具体步骤包括：
确定搜索范围：初始时，搜索范围为整个数组。
计算中间位置：通过计算搜索范围的起始索引和结束索引的平均值（或中间值），确定当前搜索范围的中间位置。
比较中间元素与目标值：
如果中间元素等于目标值，则查找成功，返回中间位置的索引。
如果中间元素大于目标值，则说明目标值在左半部分（如果存在的话），更新搜索范围为左半部分。
如果中间元素小于目标值，则说明目标值在右半部分（如果存在的话），更新搜索范围为右半部分。
重复上述步骤，直到找到目标值或搜索范围为空（即未找到目标值）。
2. 实现方式
二分查找可以通过迭代或递归两种方式实现。迭代方式较为直观，通过循环逐步缩小搜索范围；递归方式则通过函数调用自身来实现搜索范围的缩小。
二、时间复杂度分析
二分查找的时间复杂度为O(log n)，其中n为数组的长度。这是因为每次迭代或递归调用都会将搜索范围缩小一半，
所以最坏情况下（即目标值不存在于数组中）需要进行的比较次数为log n（以2为底）。因此，二分查找在处理大量数据时具有极高的效率。
三、空间复杂度分析
二分查找的空间复杂度为O(1)，即常数级空间复杂度。这是因为算法在执行过程中只需要存储几个变量（如左右边界索引、中间索引等），
这些变量的数量与数组的长度无关。因此，无论数组的长度如何变化，算法的空间复杂度都保持不变。
然而，如果采用递归方式实现二分查找，并且考虑递归调用栈的空间占用，那么空间复杂度将变为O(log n)。但在大多数情况下，我们主要关注算法本身所需的空间复杂度，即O(1)。
四、总结
二分查找是一种基于有序数组的高效搜索算法，具有O(log n)的时间复杂度和O(1)的空间复杂度。它通过每次比较数组中间的元素与目标值，将搜索范围缩小一半，
从而实现对数据的快速查找。在实际应用中，二分查找被广泛用于各种需要快速查找的场景，如数据库查询、搜索引擎等
'''
class Solution:
    def binary_search(self, nums, target):
        left, right = 0, len(nums) - 1  #右边界注意数组下标n-1
        while left <= right:
            mid = left + (right - left) // 2    #防止溢出，不使用（right+left)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1
#示例
if __name__ == '__main__':
    nums = [1, 3, 5, 7, 8,9,10]
    target = 11
    print(Solution().binary_search(nums, target))